package leecode

import (
	"math/rand"
	"sort"
)

type keyValue struct {
	key   int
	value int
}

func topKFrequent(nums []int, k int) []int {
	quickSort3(nums)
	resultMap := make(map[int]int, k) //key为数组中的元素,value为出现的次数
	result := make([]int, 0, k)
	value := make([]keyValue, 0, len(nums))
	for _, num := range nums {
		resultMap[num] = resultMap[num] + 1
	}
	for key, val := range resultMap {
		value = append(value, keyValue{key: key, value: val})
	}
	//对包含键值对的切片按值进行排序
	sort.Slice(value, func(i, j int) bool {
		return value[i].value > value[j].value
	})
	//获取前k个元素
	for i := 0; i < k; i++ {
		result = append(result, value[i].key)
	}
	return result
}

func quickSort3(nums []int) {
	if nums == nil || len(nums) < 2 {
		return
	}
	quickHelper3(nums, 0, len(nums)-1)
}
func quickHelper3(nums []int, left, right int) {
	if left < right {
		pivotIndex := left + rand.Intn(right-left+1)
		nums[pivotIndex], nums[right] = nums[right], nums[pivotIndex]
		p := partition3(nums, left, right)
		quickHelper3(nums, left, p[0]-1)
		quickHelper3(nums, p[1]+1, right)
	}
}

func partition3(nums []int, left, right int) []int {
	less := left - 1 // <区的右边界
	more := right    // > 区的左边界
	pivot := nums[right]
	for left < more {
		if nums[left] < pivot {
			less++
			nums[less], nums[left] = nums[left], nums[less]
			left++
		} else if nums[left] > pivot {
			more--
			nums[more], nums[left] = nums[left], nums[more]
		} else {
			left++
		}
	}
	nums[right], nums[more] = nums[more], nums[right]
	return []int{less + 1, more}
}
